HNOI2015 解题报告

T1 菜肴制作

Description

nn 道菜和有 mm 条要求,每条要求形如“A 号菜需要在 B 号菜的前面”。现在要求给出一个上菜序列,在满足所有要求的前提下,满足:

CF932G Palindrome Partition

Description

给定一个串,把串分成偶数段,假设为 s1,s2,,sks_1,s_2,\cdots,s_k ,要求满足 s1=sk,s2=sk1,s_1=s_k,s_2=s_{k-1},\cdots ,求方案数。
n105n\leq 10^5

Solution

阅读全文 »

一类树形 dp 方程的可换根化处理

换根 dp 是一个广为流传的算法。
换根 dp 对于 dp 方程是有要求的,一般而言 dp 方程中只能含有常数和与 i 的子树有关的项。
本文将探讨对于下述方程如何使其可以换根处理

f[p]=(ewe×f[son])+deppf[p]=(\sum_{e} w_e\times f[son])+\text{dep}_p

阅读全文 »

Luogu4299 首都

Description

nn 个点,初始时互不连通。有 qq 次操作,分别为如下三种类型:

Quiz 0107 Summary

T1 word

Description

你有一个由小写字母组成的长度为 nn 的字符串。每一步你要找到它的子串中最短的重复块(一个重复块由一个字符串与自身连接而成)。如果有多于一个,你必须选择最左边的那个。你要将那个形如 XX(X - 某个字符串)的重复块替换成 X,即删除其中的一个 X。重复以上步骤直到字符串中不存在重复块。
输出最终的字符串。

阅读全文 »

CF700E Cool Slogans

Description

给定长度为 nn 的字符串 s ,要求构造字符串序列 s1,s2,,sks_1,s_2,\cdots,s_k ,满足 i[1,k]\forall i\in[1,k]sis_i 是 s 的子串,且 i[2,k]\forall i\in[2,k], 都有 si1s_{i-1}sis_i 中至少出现了两次(可以有重叠部分)。sis_i 不能为空。求最大的 kk 值。
1n2×1051\leq n\leq 2\times 10^5

Solution

阅读全文 »

[SHOI2014] 三叉神经树

Description

给定一棵以 11 为根的有 3n+13n+1 个节点的树,树上每个节点均有一个输出端。树上有 nn 个节点有 33 个子节点,其余的 2n+12n+1 个节点无子节点(也就是叶子)。2n+12n+1 个节点的初始值均为 0/10/1 ,并且已经提前知道;剩余 nn 个节点的值为其 33 个子节点中出现次数最多的值。qq 次询问,每次改变一个叶子节点的值,求操作后根节点的值。
n,q5×105n,q\leq 5\times 10^5

Solution

阅读全文 »

[NOI2018] 你的名字

Description

给定字符串 s 。有 qq 个询问,每个询问形如 t l rt\ l\ r ,表示查询字符串 t 中有多少个本质不同的子串在 s[l:r]出现过。
q,s,t5×105q,|s|,|t|\leq 5\times 10^5

Solution

阅读全文 »

CF526D Om Nom and Necklace

Description

给定长度为 n 的字符串 s ,对于 s 的每个前缀,求该前缀是否能满足 AB...ABA 的形式,其中 A 恰好有 k+1 个,B 恰好有 k 个 。A B 可以是任意字符串,或者为空串;k 是给定的。
1n,k1061\leq n,k\leq 10^6

Solution

阅读全文 »